#if !defined( TREE_EXTRACT_SUB_TREE_H)
#define  TREE_EXTRACT_SUB_TREE_H

// standard headers
#include <vector>
#include <cassert>
//#include <ext/hash_set>
#include <tr1/unordered_set>


// component headers
#include <tree.h>


namespace bcpp_tree_ops
{




//________________________________________________________________________________________

//	op_extract_sub_trees

//		go through a tree and optimize all branches with fewer leaves than max_tree_size

//________________________________________________________________________________________
class op_extract_branches
{
    const bcpp_tree::t_tree&	tree;
	unsigned						max_tree_size;
	float							max_tree_len;
public:
	std::vector<unsigned>   		node_UIDs;
	unsigned						cnt_tree_extracted_by_size;
	unsigned						cnt_tree_extracted_by_len;
	void							inc_branch_count(bool too_long)
	{
		if (too_long)
		{
			cnt_tree_extracted_by_len++;
			last_branch_too_long = true;
		}
		else
		{
			cnt_tree_extracted_by_size++;
			last_branch_too_long = false;
		}

	}
	bool							last_branch_too_long;
	op_extract_branches(	const bcpp_tree::t_tree&	tree_,
							unsigned						max_tree_size_,
							float							max_tree_len_):
			tree(tree_),
			max_tree_size(max_tree_size_),
			max_tree_len(max_tree_len_),
			cnt_tree_extracted_by_size(0),
            cnt_tree_extracted_by_len(0)
	{
		start_at(*tree.get_root());
	}

	// use pointer because it might change
	void start_at(bcpp_tree::t_node& node);
	bool recurse(bcpp_tree::t_node& node, float& branch_len, unsigned& branch_leaf_count);
	void save_sub_tree(bcpp_tree::t_node& node);
};

//________________________________________________________________________________________

//	op_nh_strm_post_branch_extract

//________________________________________________________________________________________
//typedef __gnu_cxx::hash_set<unsigned> t_hash_uint;
typedef std::tr1::unordered_set<unsigned> t_hash_uint;

struct op_nh_strm_post_branch_extract
{
	std::ostream&						os;
	t_hash_uint   						node_UIDs;
	std::vector<bcpp_tree::t_node*> nodes;
	unsigned							cnt_sub_trees;
	unsigned							sub_tree_index_offset;

	op_nh_strm_post_branch_extract(	std::ostream&			os_,
									std::vector<unsigned>&	node_UIDs_,
									unsigned 				sub_tree_index_offset_) :
						os(os_), node_UIDs(node_UIDs_.begin(), node_UIDs_.end()),
						cnt_sub_trees(0),
						sub_tree_index_offset(sub_tree_index_offset_)
	{
	}
	void operator()(bcpp_tree::t_node* root);
	void recurse(bcpp_tree::t_node* node);
	std::string sub_tree_name(unsigned i);

};


}
#endif
